package C052;

/**
 * ClassName: C04
 * Package: C052
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/3/28 17:13
 * @Version 1.0
 * @Since 1.0
 */
public class C04 {
    public static void main(String[] args) {
//        int[] arr = {1, 7,7,7};
        int[] arr = {2,1,5,6,2,3};
        System.out.println(largestRectangleArea(arr));
    }

    static int r = 0, MAXLEN = 100001;
    static int[] stack = new int[MAXLEN];
    static int[][] res = new int[MAXLEN][2];
    static int n;
    public static int largestRectangleArea(int[] heights) {
        int pop, l;
        int ans = 0;
        n = heights.length;
        // 单调栈 计算
        for (int i = 0; i < n; i++) {
            while(r > 0 && heights[i] <= heights[stack[r - 1]]) {
                pop = stack[--r];
                l = r == 0 ? -1 : stack[r - 1];
                ans = Math.max(ans, heights[pop] * (i - l - 1));
            }
            stack[r++] = i;
        }
        // 处理剩余的栈的内容
        while(r > 0) {
            pop = stack[--r];
            l = r == 0 ? -1 : stack[r - 1];
            ans = Math.max(ans, heights[pop] * (n - l - 1));
        }
        return ans;
    }


}
